public class FindPivotIndex {
    // 寻找数组的中心下标 https://leetcode.cn/problems/find-pivot-index/description/
    public int pivotIndex(int[] nums) {
        // 先遍历一遍数组求和
        double sum=0;
        for(int i=0;i<nums.length;i++) {
            sum+=nums[i];
        }
        // 建立前缀和数组
        int[] dp=new int[nums.length+1];
        for(int i=1;i<dp.length;i++) {
            dp[i]=dp[i-1]+nums[i-1];
        }
        // 遍历前缀和数组,寻找合适的位置
        int i=0;
        for(;i<dp.length-1;i++) {
            double tar=(sum-nums[i])/2;
            if(dp[i]==tar) {
                return i;
            }
        }
        return -1;
    }

    // 另一种解法:
    public int pivotIndex2(int[] nums) {
        //计算前缀和数组
        int[] prefix=new int[nums.length];
        prefix[0]=0;
        for(int i=1;i<nums.length;i++) {
            prefix[i]=prefix[i-1]+nums[i-1];
        }
        // 计算后缀和
        int[] suffix=new int[nums.length];
        suffix[nums.length-1]=0;
        for(int i=nums.length-2;i>=0;i--) {
            suffix[i]=suffix[i+1]+nums[i+1];
        }
        // 遍历数组,比较前缀和和后缀和
        for(int i=0;i<nums.length;i++) {
            if(prefix[i]==suffix[i]) return i;
        }
        return -1;
    }

    // 解法3:空间复杂度为O(1),更优秀
    public int pivotIndex3(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 如果左侧和等于右侧和
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }

}
